#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

/* 1 静态顺序表 ：
     定长的数组
*/

struct SeqList
{
    int arr[100]; //存储空间
    int size;     //当前长度（有效数据个数）
}

//============================================================================================================

/* 2 动态顺序表 ：
     不定长的数组
     需要动态申请内存空间

     SLDataType* arr 是一个指向 SLDataType 类型的指针，(int * arr)
     它的作用是指向顺序表实际存储数据的动态开辟的内存空间（通常是通过 malloc、realloc 等函数分配的)
*/

typedef int SLDataType; //顺序表存储的数据类型，把int重命名成SLDataType，方便后期修改数据类型
typedef struct SeqList  //定义顺序表结构体类型
{
    SLDataType* arr;    //存储空间，动态申请的数组
    int size;          //当前长度(有效数据个数)
    int capacity;      //容量(最大存储空间)，当前申请的空间大小
}SL;


/* ---------- 基础接口 ----------
    void SLInit(SL s)                   //初始化函数错误版
    错误原因：值传递,but s1未初始化。
    实参：s1
    SL s1;          
*/

void SLInit(SL s)   //(int a) 形参类型是SL，值传递
{
    s.arr=NULL;
    s.size=0;
    s.capcity=0;
} 

void TestInit()
{
    SL s1;          //int a; 实例化结构体对象SL
    SLInit(s1);   
}

/*  ---------- 基础接口 ----------
    void SLInit(SL* ps);                    //初始化函数正确版
    址传递，指针变量（形参）接收地址（实参）。
    &s1 表示取这个结构体变量整体的起始地址         
*/

void SLInit(SL* ps)   //(int* ps)   形参类型是SL*（指向结构体的指针），址传递
{
    assert(ps);   //断言，保证传入的指针不为空
    ps->arr=NULL;
    ps->size=0;
    ps->capcity=0;
}

/*  结构体两种访问成员模式：
    1. 值传递：结构体变量.成员名  (不修改结构体，只访问成员)
    2. 址传递：结构体指针->成员名 （依靠指针修改结构体成员）
*/

void TestInit()
{
    SL s1;
    SLInit(&s1);   //传入s1的地址
}
//============================================================================================================
/* 
    void SLDestroy(SL* ps);                    
    函数名称：销毁函数
    函数作用：动态申请的数组空间需要手动释放
*/

void SLDestroy(SL* ps)
{
    assert(ps);
    if(ps->arr)  
    {
        free(ps->arr);
    }     
    ps->arr=NULL;   //释放后将指针置为空
    ps->size=0;
    ps->capacity=0;
}

/* ---------- 增删查改 接口 ----------
    void SLPushBack(SL* ps,SLDataType x);                   
    函数名称：尾插函数
    参数：（被插入的顺序表，插入值）

    void SLCheckCapacity(SL* ps);                   
    函数名称：检查容量函数
    参数：（which顺序表）

    问题1：
    malloc calloc realloc free ？
    -->涉及增容用realloc。
    malloc calloc都是申请空间：malloc申请一块空间，calloc是申请一块空间并且初始化这块空间，但是没有增容的概念。
    
    void* realloc(void* ptr, size_t size);
    功能：调整 ptr 指向的动态内存块的大小为 size 字节。
    返回值：成功则返回调整后内存块的起始地址（可能与原地址相同，也可能不同）；失败则返回 NULL，原内存块保持不变
    
    问题2：
    增容多少？
    -->通常是当前容量的2-3倍。

    问题3：
    返回值强转  (SLDataType*)

    问题4：
    ps->capacity初始=0怎么办？
    newCapacity 4：中庸

    问题5：
    realloc失败怎么办？

    问题6：
    ps->arr改为临时变量tmp？-->避免realloc失败时，ps->arr丢失原有地址，造成内存泄漏。

*/

void SLPushBack(SL* ps,SLDataType x)
{
    assert(ps):
    SLCheckCapacity(ps); //检查容量，确保有足够空间插入数据
    /* 写法一 */
    ps->arr[ps->size]=x;   //ps->arr：访问到ps的arr。在arr下标为size的位置插入x。
    ps->size++;
    /* 写法二 */
    ps->arr[ps->size++]=x;  //后置++：先插入x，再后移  （后置：先执行操作，再++）
}

/* 检查容量函数:判断空间够不够，不够则自动扩容。 有问题*/
void SLCheckCapacity(SL* ps)
{
    if(ps->size == ps->capacity)    // 空间不够，需要扩容
    {
         //先确定用realloc增容，问题2：增容多少？
         int newCapacity = ps->capacity == 0 ? 4 :ps->capacity * 2; //如果初始空间是0，则给上一个空间，否则直接扩容2倍
         ps->arr =(SLDataType*) realloc(ps->arr,newCapacity * sizeof(SLDataType));
         //用来替代：ps->arr =(SLDataType*) realloc(ps->arr,ps->capacity * 2 * sizeof(SLDataType)); //扩大2倍空间 4 * 2 * sizeof(int)
         if(ps->arr == NULL) //申请失败
         {
             perror("realloc fail");
             exit(1);   //退出
         }
    }
}

/* 检查容量函数 完整写法*/
void SLCheckCapacity(SL* ps)
{
    if(ps->size == ps->capacity)
    {
        //需要扩容
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->arr,newCapacity * sizeof(SLDataType));
        if(tmp == NULL)
        {
            perror("realloc fail");
            exit(1);    //直接退出，程序终止
        }
        //否则tmp != NULL，说明申请成功
        ps->arr=tmp;    //指针类型相同，可以互相给，把tmp给arr。即让arr指向新空间
        ps->capacity=newCapacity; //更新容量
    }
}

/* ---------- 增加接口 ----------
    void SLPushFront(SL* ps,SLDataType x);                   
    函数名称：头插函数
    参数：（被插入的顺序表，插入值）
    
*/
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps); //检查容量，必要时扩容
    /*
        头插需要把所有元素往后挪动一位
        终止条件：最后一次让arr[1] = arr[0]，即最后一次i=1；
    */
    for(int i=ps->size;i;i--)
    {
        ps->arr[i]=ps->arr[i-1];    //起始条件：后面赋值给前面，从前往后依次挪动
                                    //结束条件不确定，先用i占位

    }
    //此时arr[0]位置空出来了
    arr[0] = x;
    ps->size++; //有效元素个数加1
}

//完整版
void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps); //检查容量，必要时扩容
    /*
        头插需要把所有元素往后挪动一位
        终止条件：最后一次让arr[1] = arr[0]，即最后一次i=1；所以i>0
        终止条件确定后，写出完整的for循环
        不知道结束条件时候：先写起始条件和内部代码，再确定结束条件
    */
    for(int i=ps->size; i > 0 ; i--)
    {
        ps->arr[i]=ps->arr[i-1];    //起始条件：后面赋值给前面，从前往后依次挪动
    }
    //此时arr[0]位置空出来了
    arr[0] = x;
    ps->size++; //有效元素个数加1
}

/* ---------- 功能接口 ----------
    void SLPrint(SL s)                  
    不需要传递指针，因为无需通过指针修改顺序表内容，直接值传递打印就好。
    
*/
void SLPrint(SL s)
{
    for(int i=0; i<s.size;i++)
    {
        printf("%d ",s.arr[i]); //s.arr[i]：访问到s的arr
    }
    printf("\n");
}


/* ---------- 删除接口 ----------
    删除的话也要传指针，因为要修改顺序表内容
    SL* ：指向顺序表的指针

    void SLPopBack(SL* ps);                   
    函数名称：尾删函数
    参数：（被删除的顺序表）

    void SLPopFront(SL* ps);                   
    函数名称：头删函数
    参数：（被删除的顺序表）
    
*/
void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);   //通过size判断顺序表不为空
    //走到这里，说明顺序表不为空
    ps->arr[ps->size -1]=-1; //最后一个元素给上-1，表示无效     这句话要不要都行，因为size减1后，外界访问不到这个位置了，不会影响顺序表的其他操作。
    ps->size--; //最后有效元素个数减1
}

void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size); //保证顺序表不为空

    /*
        头删需要把所有元素往前挪动一位,此时也就覆盖了arr[0]

    */
   for(int i=0; i ; i++)
   {
        ps->arr[i] = ps->arr[i+1];
   }
}

//完整版
void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size); //保证顺序表不为空

    /*
        头删需要把所有元素往前挪动一位,此时也就覆盖了arr[0]
        初始条件：arr[0] = arr[1]
        终止条件：arr[size-2] = arr[size-1]，所以 i = size-2 <size-1
    */
   for(int i=0; i < size-1; i++)
   {
        ps->arr[i] = ps->arr[i+1];
   }
    ps->size--; //有效元素个数减1
}

/*---------- 在指定位置之前插入数据 接口 ----------
    参数：被插入的顺序表，插入位置（顺序表的下标），插入值
    注意：
    pos必须>=0，不能为负数 -1 0 100
    pos必须<=size，由于是在指定位置之前插入数据，
    所以允许pos等于size，即在最后位置之后插入数据，相当于尾插。
    //顺序表：   1 2 size=2
    //下标pos：  0 1  
    i--：因为从后往前挪动
    第一次：arr[size] = arr[size-1] i=size
    第二次：arr[size-1] = arr[size-2]
    最后一次：arr[pos+1] = arr[pos]，把pos这个数据空出来--》结束条件：i=pos+1，i走不到pos，i>pos
*/
//只写了开始条件
void SLInsert(SL* ps,int pos,SLDataType x)
{
    assert(ps);
    assert(pos >=0 pos < = ps-> size);
    //插入数据：空间够不够
    SLCheckCapacity(ps);
    //空间够了，直接插入：
    //step1：把pos及其之后的数据整体往后挪动一位
    for(int i=ps->size; i ;i--) //i--：因为从后往前挪动
    {
        ps->arr[i] = ps->arr[i-1];  

    }
    
    //step2:
    //step3:

}

//完整版
void SLInsert(SL* ps,int pos,SLDataType x)
{
    assert(ps);
    assert(pos >=0 pos < = ps-> size);
    //插入数据：空间够不够
    SLCheckCapacity(ps);
    //空间够了，直接插入：
    //step1：把pos及其之后的数据整体往后挪动一位
    for(int i=ps->size; i > pos  ;i--) //i--：因为从后往前挪动
    {
        ps->arr[i] = ps->arr[i-1];  

    }
    //step2:插入x进入pos位置
    ps->arr[pos] = x;
    //step3:
    ps-size++;
}

void TestInseRT()
{
    SL s1;
    SLInit(&s1);
    SLPushBack(&s1,1);
    SLPushBack(&s1,2);
    SLPushBack(&s1,3);
    SLPushBack(&s1,4);
    SLPrint(s1); //1 2 3 4
    SLInsert(&s1,0,100); //
     SLInsert(&s1,s.size,99);
    SLPrint(s1);    //100 1 2 3 4 99
   

    //
    SLErase(&s1,0); //删除位置0
    
    //
    int find = SLFind(&s1,3);
    if(find<0)
    {
        printf("没有找到3\n");
    }
    else
    {
        printf("找到了3，下标是：%d\n",find);
    }
     SLDestroy(&s1);
}

/*---------- 删除指定位置的数据 接口 ----------
    参数：被删除的顺序表，删除位置（顺序表的下标）
    注意：
    一开始：ps->arr[pos] = ps->arr[pos+1]
           ps->arr[pos+1]=ps->arr[pos+2]
           ...
    结束：ps->arr[ps->size-2] = ps->arr[ps->size-1] i=size-2,i<size-1
    size--
*/
void SLErase(SL* ps,int pos)
{
    assert(ps);
    assert(pos>=0 && pos< ps->size);
    for(int i=pos;i < ps->size-1;i++ )
    {
        ps->arr[i] = ps->arr[i+1];  // 
    }
    //
    ps->size--;
}

/*---------- 查找指定位置的数据 接口 ----------
         参数：查找顺序表，要查找的数据
         方式：遍历数据表查找
*/
void SLFind(SL* ps,SLDataType x)
{
    assert(ps);
    for(int i=0;i<ps->size;i++)
    {
        if(ps->arr[i] == x)
        {
            return i;  //找到了，返回下标
        }
    }
    //没有找到
    return -1;  //返回无效下标-1
}

void main()
{
    TestInit();
    SLPushFront(&s1,10);
    SLPrint(s1);
    SLPushBack(&s1,20);
    SLPrint(s1);
    SLDestroy(&s1);
    return 0;
}


//============================================================================================================


